package com.leetcode.dfs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Leetcode216 {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (n > 45) {
            return res;
        }
        dfs(k, n, 1, 0, new LinkedList<>());
        return res;
    }

    private void dfs(int k, int n, int index, int sum, LinkedList<Integer> path) {
        if (path.size() == k) {
            if (sum == n) {
                res.add(new LinkedList<>(path));
            }
            return;
        }

        for (int i = index; i<=9; i++) {
            if (sum + i > n) {
                break;
            }
            path.add(i);
            sum += i;
            dfs(k, n, i+ 1, sum, path);
            sum -= i;
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        Leetcode216 leetcode216 = new Leetcode216();
        List<List<Integer>> ans =leetcode216.combinationSum3(3, 9);
        System.out.println(ans);
    }
}
